test.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "import chromadb\n",
    "from tqdm import tqdm\n",
    "from langchain_community.chat_models import ChatOllama\n",
    "from langchain_community.document_loaders import PyPDFLoader\n",
    "from langchain_community.embeddings import OllamaEmbeddings\n",
    "from langchain_community.vectorstores import Chroma\n",
    "from langchain_community.chat_message_histories import ChatMessageHistory\n",
    "from langchain_text_splitters import RecursiveCharacterTextSplitter\n",
    "from langchain_core.runnables.history import RunnableWithMessageHistory\n",
    "from langchain_core.prompts import ChatPromptTemplate, MessagesPlaceholder\n",
    "from langchain_core.chat_history import BaseChatMessageHistory\n",
    "from langchain.chains import create_retrieval_chain, create_history_aware_retriever\n",
    "from langchain.chains.combine_documents import create_stuff_documents_chain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "llm = ChatOllama(model=\"llama2:7b\")\n",
    "emb = OllamaEmbeddings(model=\"llama2:7b\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "AIMessage(content=\"\\nHello there! It's nice to meet you. Is there something I can help you with or would you like to chat?\", response_metadata={'model': 'llama2:7b', 'created_at': '2024-04-10T09:30:17.182952Z', 'message': {'role': 'assistant', 'content': ''}, 'done': True, 'total_duration': 2190328083, 'load_duration': 1943125, 'prompt_eval_duration': 225608000, 'eval_count': 28, 'eval_duration': 1961974000}, id='run-b445cf2d-3c04-4d9a-b59b-2c74510897c0-0')"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "llm.invoke(\"Hello world!\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class OllamaEmbeddingFn(chromadb.EmbeddingFunction):\n",
    "    def __call__(self, input: chromadb.Documents) -> chromadb.Embeddings:\n",
    "        return emb.embed_documents(input)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# initialise chroma collection\n",
    "# adapted from https://docs.trychroma.com/usage-guide#using-collections\n",
    "client = chromadb.PersistentClient(path=\"documents/chroma_db\")\n",
    "collection = client.get_or_create_collection(\n",
    "    name=\"helpsheets\", embedding_function=OllamaEmbeddingFn()\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# paths of documents to index\n",
    "helpsheet_dir = r\"documents/helpsheet collection\"\n",
    "helpsheet_paths = [\n",
    "    f\n",
    "    for f in os.listdir(helpsheet_dir)\n",
    "    if os.path.isfile(os.path.join(helpsheet_dir, f))\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "0it [00:00, ?it/s]Ignoring wrong pointing object 11 0 (offset 0)\n",
      "Ignoring wrong pointing object 14 0 (offset 0)\n",
      "Ignoring wrong pointing object 41 0 (offset 0)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 9 - AVL Trees and Balancing.pdf\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "1it [00:25, 25.03s/it]Ignoring wrong pointing object 11 0 (offset 0)\n",
      "Ignoring wrong pointing object 14 0 (offset 0)\n",
      "Ignoring wrong pointing object 29 0 (offset 0)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 10 - Graphs.pdf\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "2it [00:47, 23.75s/it]Ignoring wrong pointing object 11 0 (offset 0)\n",
      "Ignoring wrong pointing object 23 0 (offset 0)\n",
      "Ignoring wrong pointing object 34 0 (offset 0)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 7 - Set and UFDS.pdf\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "3it [01:00, 18.82s/it]Ignoring wrong pointing object 11 0 (offset 0)\n",
      "Ignoring wrong pointing object 32 0 (offset 0)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 4 - Lists Stacks and Queues.pdf\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "4it [01:23, 20.44s/it]Ignoring wrong pointing object 11 0 (offset 0)\n",
      "Ignoring wrong pointing object 46 0 (offset 0)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 8 - Ordered Map and BST.pdf\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "5it [01:54, 24.18s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 cs3230-cheatsheet.pdf\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "6it [04:16, 64.24s/it]Ignoring wrong pointing object 11 0 (offset 0)\n",
      "Ignoring wrong pointing object 14 0 (offset 0)\n",
      "Ignoring wrong pointing object 26 0 (offset 0)\n",
      "Ignoring wrong pointing object 29 0 (offset 0)\n",
      "Ignoring wrong pointing object 36 0 (offset 0)\n",
      "Ignoring wrong pointing object 38 0 (offset 0)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6 12 - Minimum Spanning Tree.pdf\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "7it [04:45, 52.68s/it]Ignoring wrong pointing object 11 0 (offset 0)\n",
      "Ignoring wrong pointing object 22 0 (offset 0)\n",
      "Ignoring wrong pointing object 38 0 (offset 0)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7 6 - Priority Queue and Binary Heap.pdf\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "8it [05:09, 43.59s/it]Ignoring wrong pointing object 10 0 (offset 0)\n",
      "Ignoring wrong pointing object 13 0 (offset 0)\n",
      "Ignoring wrong pointing object 30 0 (offset 0)\n",
      "Ignoring wrong pointing object 32 0 (offset 0)\n",
      "Ignoring wrong pointing object 35 0 (offset 0)\n",
      "Ignoring wrong pointing object 42 0 (offset 0)\n",
      "Ignoring wrong pointing object 45 0 (offset 0)\n",
      "Ignoring wrong pointing object 53 0 (offset 0)\n",
      "Ignoring wrong pointing object 55 0 (offset 0)\n",
      "Ignoring wrong pointing object 62 0 (offset 0)\n",
      "Ignoring wrong pointing object 81 0 (offset 0)\n",
      "Ignoring wrong pointing object 88 0 (offset 0)\n",
      "Ignoring wrong pointing object 95 0 (offset 0)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8 13 - Single Source Shortest Path.pdf\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "9it [06:15, 50.51s/it]Ignoring wrong pointing object 11 0 (offset 0)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9 5 - HashTable and Collisions.pdf\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "10it [06:40, 42.83s/it]Ignoring wrong pointing object 10 0 (offset 0)\n",
      "Ignoring wrong pointing object 39 0 (offset 0)\n",
      "Ignoring wrong pointing object 41 0 (offset 0)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 3 - Arrays and Linked Lists.pdf\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "11it [07:13, 39.70s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "11 cs2040s-cheatsheet.pdf\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "12it [08:15, 46.58s/it]Ignoring wrong pointing object 10 0 (offset 0)\n",
      "Ignoring wrong pointing object 12 0 (offset 0)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12 2 - Sorting.pdf\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "13it [08:23, 34.84s/it]Ignoring wrong pointing object 11 0 (offset 0)\n",
      "Ignoring wrong pointing object 23 0 (offset 0)\n",
      "Ignoring wrong pointing object 30 0 (offset 0)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13 1 - Complexities and Searching.pdf\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "14it [08:48, 31.68s/it]Ignoring wrong pointing object 11 0 (offset 0)\n",
      "Ignoring wrong pointing object 14 0 (offset 0)\n",
      "Ignoring wrong pointing object 29 0 (offset 0)\n",
      "Ignoring wrong pointing object 36 0 (offset 0)\n",
      "Ignoring wrong pointing object 43 0 (offset 0)\n",
      "Ignoring wrong pointing object 51 0 (offset 0)\n",
      "Ignoring wrong pointing object 54 0 (offset 0)\n",
      "Ignoring wrong pointing object 56 0 (offset 0)\n",
      "Ignoring wrong pointing object 67 0 (offset 0)\n",
      "Ignoring wrong pointing object 74 0 (offset 0)\n",
      "Ignoring wrong pointing object 77 0 (offset 0)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "14 11 - Graph Operations and Analysis.pdf\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "15it [09:43, 38.89s/it]\n"
     ]
    }
   ],
   "source": [
    "text_splitter = RecursiveCharacterTextSplitter(chunk_size=1000, chunk_overlap=200)\n",
    "\n",
    "# index documents (takes forever)\n",
    "# adapted from https://python.langchain.com/docs/modules/data_connection/document_loaders/pdf/#using-pypdf\n",
    "if collection.count() == 0:\n",
    "    for i, hs_path in tqdm(enumerate(helpsheet_paths)):\n",
    "        print(i, hs_path)\n",
    "        # load document\n",
    "        loader = PyPDFLoader(os.path.join(helpsheet_dir, hs_path))\n",
    "        docs = loader.load()\n",
    "        # split document into chunks\n",
    "        splits = text_splitter.split_documents(docs)\n",
    "        # unique ids for each chunk\n",
    "        ids = [f\"{i} - {j}\" for j in range(len(splits))]\n",
    "        # add chunks into chroma collection\n",
    "        collection.add(\n",
    "            ids=ids,\n",
    "            metadatas=[d.metadata for d in splits],\n",
    "            documents=[d.page_content for d in splits],\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# initialise langchain vector store from chroma client\n",
    "# adapted from https://python.langchain.com/docs/integrations/vectorstores/chroma/#passing-a-chroma-client-into-langchain\n",
    "vectorstore = Chroma(\n",
    "    client=client,\n",
    "    collection_name=\"helpsheets\",\n",
    "    embedding_function=emb,\n",
    ")\n",
    "retriever = vectorstore.as_retriever()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# code for chat history (including next 2 code blocks)\n",
    "# adapted from https://python.langchain.com/docs/use_cases/question_answering/chat_history/\n",
    "contextualize_q_system_prompt = \"\"\"Given a chat history and the latest user question \\\n",
    "which might reference context in the chat history, formulate a standalone question \\\n",
    "which can be understood without the chat history. Do NOT answer the question, \\\n",
    "just reformulate it if needed and otherwise return it as is.\"\"\"\n",
    "contextualize_q_prompt = ChatPromptTemplate.from_messages(\n",
    "    [\n",
    "        (\"system\", contextualize_q_system_prompt),\n",
    "        MessagesPlaceholder(\"chat_history\"),\n",
    "        (\"human\", \"{input}\"),\n",
    "    ]\n",
    ")\n",
    "history_aware_retriever = create_history_aware_retriever(\n",
    "    llm, retriever, contextualize_q_prompt\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "qa_system_prompt = \"\"\"You are a computer science tutoring assistant for question-answering tasks. \\\n",
    "Use the following pieces of retrieved context to answer the question. \\\n",
    "Do not mention \"the context\". \\\n",
    "If you don't know the answer, just say that you don't know. \\\n",
    "Use five sentences maximum and keep the answer concise.\\\n",
    "\n",
    "{context}\"\"\"\n",
    "qa_prompt = ChatPromptTemplate.from_messages(\n",
    "    [\n",
    "        (\"system\", qa_system_prompt),\n",
    "        MessagesPlaceholder(\"chat_history\"),\n",
    "        (\"human\", \"{input}\"),\n",
    "    ]\n",
    ")\n",
    "\n",
    "\n",
    "question_answer_chain = create_stuff_documents_chain(llm, qa_prompt)\n",
    "\n",
    "rag_chain = create_retrieval_chain(history_aware_retriever, question_answer_chain)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Statefully manage chat history ###\n",
    "store = {}\n",
    "\n",
    "\n",
    "def get_session_history(session_id: str) -> BaseChatMessageHistory:\n",
    "    if session_id not in store:\n",
    "        store[session_id] = ChatMessageHistory()\n",
    "    return store[session_id]\n",
    "\n",
    "\n",
    "conversational_rag_chain = RunnableWithMessageHistory(\n",
    "    rag_chain,\n",
    "    get_session_history,\n",
    "    input_messages_key=\"input\",\n",
    "    history_messages_key=\"chat_history\",\n",
    "    output_messages_key=\"answer\",\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# streams llm output\n",
    "# adapted from https://python.langchain.com/docs/use_cases/question_answering/streaming/\n",
    "def query_and_print(input: str, session_id=\"abc123\"):\n",
    "    for chunk in conversational_rag_chain.stream(\n",
    "        {\"input\": input},\n",
    "        config={\n",
    "            \"configurable\": {\"session_id\": session_id}\n",
    "        },  # constructs a key \"abc123\" in `store`.\n",
    "    ):\n",
    "        if \"answer\" in chunk:\n",
    "            print(chunk[\"answer\"], end=\"\")\n",
    "        else:\n",
    "            print(chunk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'input': 'What did i ask you just now?'}\n",
      "{'chat_history': [HumanMessage(content='What is an MST?'), AIMessage(content=\"An MST (Minimum Spanning Tree) is a subgraph of a graph that connects all the vertices together while minimizing the total weight of the edges. In other words, it is a subset of the edges of the original graph that connect all the vertices together in a way that minimizes the sum of the weights of the edges.\\n\\nFor example, consider a graph with 5 vertices labeled A, B, C, D, and E, and 7 edges: AB, AC, AD, BE, BC, BD, and DE. The MST of this graph would be the subset of edges that connects all the vertices together in a way that minimizes the total weight of the edges. In this case, the MST would be {AB, AC, AD, BD}, which has a total weight of 4.\\n\\nMSTs have many applications in graph theory and computer science, such as:\\n\\n* Network flow optimization: MSTs can be used to optimize network flow problems by finding the minimum cost flow that satisfies all constraints.\\n* Cut algorithms: MSTs can be used to find the maximum cut of a graph, which is the maximum weight of edges that can be removed from the graph while keeping it connected.\\n* Graph clustering: MSTs can be used to cluster graphs into groups based on their connectivity patterns.\\n\\nThe time complexity of finding an MST of a graph depends on the algorithm used. Some common algorithms for finding an MST include Kruskal's algorithm, Prim's algorithm, and Boruvka's algorithm, which have time complexities of O(E+V log V), O(V+E log V), and O(E log E) respectively, where E is the number of edges and V is the number of vertices in the graph.\")]}\n",
      "{'context': [Document(page_content='the same time, although its main purpose is to allow people to push and pull from \\nboth ends conveniently.  \\nImplementation: \\nBoth Circular Arrays and Tailed LinkedList can be used. So long a reference can be \\nmaintained at the head and the tail, the addition and removal of elements can be easily done from both ends. \\n \\nImplementation using Arrays: \\nSimply maintain a front and back index, with an additional capability of adding to the front and removing from the front. \\n• addFront(item) – if not isEmpty(), front = (front+maxSize -1)%maxSize, \\narr[front] = item, else if isEmpty(), arr[front] = item. \\n• removeFront() – if isEmpty() return null, else item = arr[front], front = (front+1)%maxSize, return item. \\n \\nImplementation using LinkedList: \\nWill be the exact same as using a Tailed LinkedList, with the addFront(), addBack(), removeFront(), removeBack() functions. \\n \\nWhich implementation is better?', metadata={'page': 5, 'source': 'documents/helpsheet collection/4 - Lists Stacks and Queues.pdf'}), Document(page_content='spot through the use of a Linked List. The slot in the array would be containing the \\nhead of a Linked List, where new <key, value> pairings can be inserted accordingly.  \\n \\nSeparate Chaining Implementation: Array of Linked Lists \\nSo why an array of linked lists, and not an array of arrays? This is because a \\nLinkedList allows for overall faster insertion, searching and deletio n. \\n \\nLet’s say there are x items stored at the same hash slot. We would thus need to \\niterate through all x items to find a specific item for linked lists, while we can use \\nbinary search for array, allowing us to find the item faster.  \\n \\nHowever, the maintenance of a sorted array would be very difficult due to the need \\nto constantly shift items back and forth. On the other hand, linked list’s insertion \\nand deletion is a lot faster.  \\nFurthermore, linked list allows us to not waste space unnecessarily, which may \\noccur when we initialize arrays without more than 1 element inside.', metadata={'page': 3, 'source': 'documents/helpsheet collection/5 - HashTable and Collisions.pdf'}), Document(page_content='5. One-pass Bellman Ford’s for Directed Acyclic Graph \\nCycles are the reason for the need to repeatedly relax the edges of a graph. This is \\nbecause as the same edge can be used for multiple paths, and depending on the \\norder of edge relaxation, we may not find the shortest path f irst. \\n \\nAs such, if we happen to have a directed acyclic graph (DAG), we can actually \\nsimplify Bellman Ford’s algorithm and make it more efficient.  \\n First, we will need to topologically sort the vertices using Kahn’s Algorithm or DFS, \\nas covered previously. Then, we will simply need to run Bellman Ford’s algorithm once across all edges once in topological order. \\n \\nWe can also use the same method even if the source vertex is not the first vertex of the topological sort. We just need to ensure that the source v ertex’s distance is \\ncorrectly recorded as 0, with every other path estimate being recorded as infinity, i.e. both those before and those after the source vertex.', metadata={'page': 6, 'source': 'documents/helpsheet collection/13 - Single Source Shortest Path.pdf'}), Document(page_content='CreateHeap(Arr) \\n \\nNaïve Version – O(N log N) \\n \\n \\nStirling’s approximation states that: \\nlog 1 + log 2 + log 3 +…+ log N = log N! = N log N   \\nBetter Version – O(N) \\n \\n \\nMathematical Proof \\nTo solve for the complexity, we first need to be aware of the following:  \\n• Height of complete binary tree of size N = floor(log N) = h  \\n• Cost to run shiftDown(index) = h \\n• Number of nodes at height h (bottommost layer is 0) = ceil(N/(2^(h+1))) \\n \\nThe cost to perform createHeap is thus: \\n!\"𝑛\\n2%&\\'(𝑂(ℎ)⌊./\\t(1)⌋\\n%34 \\nThe Big-O can be taken to the outside along with n, and h can be moved on top of the fraction. We can also take out ½ as it is a constant.  \\n𝑂(𝑛!5ℎ\\n2%6⌊./(1)⌋\\n%34) \\nThe summation can be further summarised and broadened to sum till infinity (as it is an upper bound), resulting in: \\n𝑂(𝑛!𝑘𝑥9:\\n934) \\nThe right side can be evaluated to a case where x=1/2, which forms a geometric \\nseries. You can very simply sum it up: \\n𝑥\\n(1−𝑥)==2 \\nThus the time complexity is O(2N) = O(N).', metadata={'page': 3, 'source': 'documents/helpsheet collection/6 - Priority Queue and Binary Heap.pdf'})]}\n",
      "You asked me to answer the following question: Which implementation is better for a hash table with an array of linked lists?"
     ]
    }
   ],
   "source": [
    "query_and_print(\"What did i ask you just now?\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'input': \"How to solve it using Prim's algorithm?\"}\n",
      "{'chat_history': [HumanMessage(content='What is an MST?'), AIMessage(content=\"An MST (Minimum Spanning Tree) is a subgraph of a graph that connects all the vertices together while minimizing the total weight of the edges. In other words, it is a subset of the edges of the original graph that connect all the vertices together in a way that minimizes the sum of the weights of the edges.\\n\\nFor example, consider a graph with 5 vertices labeled A, B, C, D, and E, and 7 edges: AB, AC, AD, BE, BC, BD, and DE. The MST of this graph would be the subset of edges that connects all the vertices together in a way that minimizes the total weight of the edges. In this case, the MST would be {AB, AC, AD, BD}, which has a total weight of 4.\\n\\nMSTs have many applications in graph theory and computer science, such as:\\n\\n* Network flow optimization: MSTs can be used to optimize network flow problems by finding the minimum cost flow that satisfies all constraints.\\n* Cut algorithms: MSTs can be used to find the maximum cut of a graph, which is the maximum weight of edges that can be removed from the graph while keeping it connected.\\n* Graph clustering: MSTs can be used to cluster graphs into groups based on their connectivity patterns.\\n\\nThe time complexity of finding an MST of a graph depends on the algorithm used. Some common algorithms for finding an MST include Kruskal's algorithm, Prim's algorithm, and Boruvka's algorithm, which have time complexities of O(E+V log V), O(V+E log V), and O(E log E) respectively, where E is the number of edges and V is the number of vertices in the graph.\"), HumanMessage(content='What did i ask you just now?'), AIMessage(content='You asked me to answer the following question: Which implementation is better for a hash table with an array of linked lists?')]}\n",
      "{'context': [Document(page_content='spot through the use of a Linked List. The slot in the array would be containing the \\nhead of a Linked List, where new <key, value> pairings can be inserted accordingly.  \\n \\nSeparate Chaining Implementation: Array of Linked Lists \\nSo why an array of linked lists, and not an array of arrays? This is because a \\nLinkedList allows for overall faster insertion, searching and deletio n. \\n \\nLet’s say there are x items stored at the same hash slot. We would thus need to \\niterate through all x items to find a specific item for linked lists, while we can use \\nbinary search for array, allowing us to find the item faster.  \\n \\nHowever, the maintenance of a sorted array would be very difficult due to the need \\nto constantly shift items back and forth. On the other hand, linked list’s insertion \\nand deletion is a lot faster.  \\nFurthermore, linked list allows us to not waste space unnecessarily, which may \\noccur when we initialize arrays without more than 1 element inside.', metadata={'page': 3, 'source': 'documents/helpsheet collection/5 - HashTable and Collisions.pdf'}), Document(page_content='Collision \\nDue to the fact that we are hashing a large number of items to a smaller set of keys, \\nwe may encounter collisions, which is when more than one ite m gets mapped to the \\nsame key.  \\n \\nThis occurs more frequently than we would intuitively expect, as seen from Von \\nMises Paradox, where you only need 23 in a room to have >50% chance of at least 2 people sharing the same birthday. \\n \\nIn this case, we will need to resolve this collision in a way that still ensures efficiency. \\n \\nCriteria of a Good Collision Resolution Method \\n• Minimize clustering \\n• Always find an empty spot if it exists \\n• Give different probe sequences when two initial probes are the same (i.e. no \\nsecondary clustering) \\n• Fast \\n  \\nSeparate Chaining \\nThe most straightforward method is to keep storing the collided keys into the same \\nspot through the use of a Linked List. The slot in the array would be containing the \\nhead of a Linked List, where new <key, value> pairings can be inserted accordingly.', metadata={'page': 3, 'source': 'documents/helpsheet collection/5 - HashTable and Collisions.pdf'}), Document(page_content='5. One-pass Bellman Ford’s for Directed Acyclic Graph \\nCycles are the reason for the need to repeatedly relax the edges of a graph. This is \\nbecause as the same edge can be used for multiple paths, and depending on the \\norder of edge relaxation, we may not find the shortest path f irst. \\n \\nAs such, if we happen to have a directed acyclic graph (DAG), we can actually \\nsimplify Bellman Ford’s algorithm and make it more efficient.  \\n First, we will need to topologically sort the vertices using Kahn’s Algorithm or DFS, \\nas covered previously. Then, we will simply need to run Bellman Ford’s algorithm once across all edges once in topological order. \\n \\nWe can also use the same method even if the source vertex is not the first vertex of the topological sort. We just need to ensure that the source v ertex’s distance is \\ncorrectly recorded as 0, with every other path estimate being recorded as infinity, i.e. both those before and those after the source vertex.', metadata={'page': 6, 'source': 'documents/helpsheet collection/13 - Single Source Shortest Path.pdf'}), Document(page_content='graph faster than O(VE), because for every vertex, we need O(E) time to determine \\nits neighbours. \\n Proof: \\nFalse. If we sort the edge list by the starting vertex followed by the second vertex, \\nwe can potentially reduce any searching time to be O(log E) for binary search. The sorting itself will be O(E log E). This combined with the processing of N vertices \\nresults in around O(Max(V log E/E log E)). \\n We can also translate an Edge List into an Adjacency List, which takes O(E) time. \\nThen we perform BFS/DFS with Adjacency List, which takes O(V+E) time. \\n \\nClaim: A connected graph has at least E = V - 1 edges. Prove or disprove it. \\n \\nProof: \\nTrue, as V-2 edges will not allow all vertices to be connected. V -1 allows us to form \\na tree. \\n \\nClaim: A single linked list has V vertices and E-1 directed edges. These edges go \\nfrom vertex i to i + 1, where 0 <= i < (V - 1). Therefore, there is only one topological \\nsort. Prove or disprove it.', metadata={'page': 9, 'source': 'documents/helpsheet collection/11 - Graph Operations and Analysis.pdf'})]}\n",
      "To find an MST of a graph using Prim's algorithm, follow these steps:\n",
      "\n",
      "1. Initialize the tree as empty.\n",
      "2. Choose an arbitrary vertex v as the root of the tree.\n",
      "3. For each unvisited vertex u in the graph:\n",
      "a. If u is not the root, mark it as visited and add it to the tree.\n",
      "b. If u is the root, mark it as visited and add all of its neighbors that are not yet visited to the tree.\n",
      "4. After visiting all unvisited vertices, return the tree.\n",
      "\n",
      "Here's a more detailed explanation:\n",
      "\n",
      "1. Initialize the tree as empty. This means we have no edges in the tree yet.\n",
      "2. Choose an arbitrary vertex v as the root of the tree. This is the starting point for our search.\n",
      "3. For each unvisited vertex u in the graph:\n",
      "a. If u is not the root, mark it as visited and add it to the tree. This involves adding the edge connecting u to the root to the tree.\n",
      "b. If u is the root, mark it as visited and add all of its neighbors that are not yet visited to the tree. This involves adding the edges connecting the root to its neighbors to the tree.\n",
      "4. After visiting all unvisited vertices, return the tree. The resulting tree is an MST of the graph.\n",
      "\n",
      "Note: Prim's algorithm starts at a random vertex, not necessarily the root.\n",
      "\n",
      "Time complexity: O(E+V), where E is the number of edges and V is the number of vertices in the graph. This is because we need to visit each edge once and each vertex once, regardless of whether it is already visited or not."
     ]
    }
   ],
   "source": [
    "query_and_print(\"How to solve it using Prim's algorithm?\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "store.clear()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".venv",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}