CMPE 232 [Bilgi university] [Advanced Data Structures and Algorithms]

Uncategorized

About Course

This course builds on CMPE 211 to apply similar techniques to analyse more sophisticated algorithms and data structures. Topics covered include graphs and graph algorithms, greedy algorithms, random algorithms, divide and conquer algorithms, dynamic programming and string searching algorithms.

Upon successful completion of the course, students will be able to;
Analyse and compare algorithms for string matching
Analyse and compare numerical algorithms such as fast multiplication and exponentiation
Implement and compare Monte Carlo algorithms such as those for primality testing.
Recognise and define data structures for the representation of constructs such as graphs, hash tables, matrices and others. discuss and compare their implementations
Implement and analyse graph algorithms.
Implement and analyse dynamic programming algorithms.
Use amortised analysis on the time and space requirements of algorithms.

Course Content

Graphs

Graphs

01:20:00

DFS and BFS

Connected Components

DIRECTED GRAPHS introduction and API

Directed Graph Search and topological sort

Strong Components

Minimum spanning tree (greedy algorithm)

edge-weighted graph API and Kruskal’s algorithm

Prim’s algorithm

Student Ratings & Reviews

No Review Yet

No Review Yet

1 .Week Revisiting graph algorithms in detail: Undirected graphs: bipartite graph, Undirected graph data type and API, compute the degree of a vertex, compute maximum degree, compute average degree, count self-loops,
2 .Week Undirected graphs: Alternative representations, adjacency matrix, array of edges, array of adjacency lists. Adjacency-lists data structure, Depth-first search, Finding paths, Breadth-first search
3 .Week Directed graphs: Digraph data type, Reachability in digraphs, Finding paths in digraphs, Cycles and DAGs, Depth-first orders and topological sort, Strong connectivity in digraphs, Kosaraju’s algorithm
4 .Week Minimum Spanning Trees: Underlying principles, Greedy algorithm, Edge-weighted graph data type, API for MST algorithms, Prim’s algorithm (lazy version and eager version), Kruskal’s algorithm,
5 .Week Shortest Path Algorithms: Properties of shortest paths, Edge-weighted digraph data types, API and data structures for shortest path algorithms, Theoretical basis for shortest-paths algorithms, Dijkstra’s algorithm,
6 .Week Shortest paths in general edge-weighted digraphs, Bellman-Ford algorithm
7 .Week Midterm Revision
8 .Week String algorithms: String sorts, Key-indexed counting, least significant-digit first (LSD) string sort, MSD string sort, Three-way string quicksort, comparison of sorting algorithms for string sort
9 .Week Tries: Trie symbol table, node representation, insertion, deletion, collecting keys, wildcard match, Longest prefix, Alphabet, Worst-case time bound for search and insert, Ternary search tries (TSTs), Properties of TSTs, comparison of string symbol-table implementations
10 .Week Substring Search: Brute-force substring search, Knuth-Morris-Pratt substring search, DFA simulation for KMP, Boyer-Moore substring search, Rabin-Karp fingerprint search,
11 .Week Regular expressions: Describing patterns with regular expressions, Simulating a Nondeterministic finite-state automata (NFA) to implement regular expressions, Building an NFA corresponding to an RE,
12 .Week Data Compression: fundamental limitations, Universal data compression, Run-length encoding, Huffman compression, Variable-length prefix-free codes,
13 .Week Data Compression: Trie representation for prefix-free codes, Expansion for prefix-free codes, Compression for prefix-free codes, Trie construction, Huffman compression implementation, LZW compression
14 .Week Advanced topics: Event-driven simulation, B-trees, Suffix arrays, Network-flow algorithms, Ford-Fulkerson maxflow algorithm, Reduction, Linear Programming, Intractability, Non-determinism, P and NP complexity classes, Cook-Levin theorem
15 .Week Semester overview
16 .Week Final Revision

Open chat

مرحبا Ostazy
كيف يمكن ان اساعدك