CO2030 Data Structures and Algorithms II

CO2030

Data Structures and Algorithms II

3

Core

Course Content: (Only main topics & subtopics) Trees Tree ADT, linked implementation, tree traversal, efficiency of search and maintenance operations, binary search trees, balanced BSTs, AVL and red-black trees, binary heaps, priority queues, heapsort, other applications of tree data structures (abstract-syntax-trees, XML/JSON parsing, radix-trees, Huffman-trees, B-trees), using trees to represent computational problems. Graphs Graph ADT, graph types and properties, matrix and list based implementations, graph traversal (depth-first, breadth-first), efficiency of search and maintenance operations, topological sort, Eulerian and Hamiltonian cycles, spanning trees, Kruskal’s algorithm, Prim’s algorithm, greedy algorithms and local optima, shortest-path algorithms (Dijkstra’s, A*, Floyd-Warshall), reachability, Kosaraju’s algorithm, graph coloring, applications of graph data structures (in location maps, flow networks, social networks, games, etc.), using graphs to represent computational problems Hashing Associative-array (map/dictionary/set) ADT, the dictionary problem, tree implementations, hash table implementations, hash functions and codes, collision handling, efficiency of search and operations, associative-array applications (in programming languages, memoization, JSON, No-SQL databases), using hashing to efficiently solve computational problems.

● To expand the notion of efficiently representing and solving non-trivial computational problems without resorting to naïve or brute-force techniques. ● To familiarize students with real world applications of Tree, Graph and Associative-arrayADT (Abstract Data Type) based data structures and algorithms.

• Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein
• Data structures and algorithms by Aho, Hopcroft and Ullman
• Algorithms by Sedgewick and Wayne
• Algorithm Design Manual by S S Skiena