## CMPE 250 Data Structures and AlgorithmsThe CMPE 250 course is the last of the sequence of introductory programming courses at Bogazici (CMPE 150-160-250) and is one of the key courses in the entire curriculum. The focus is on algorithm design, reductions and the choice of appropriate data structures for solving computational problems. Programming methodology is based on the widely-used C++ programming language. Emphasis is on good programming style, learning the ecosystem of the C++ language and the standard template library (STL). ## Fall 2018250 WThTh634 NH 105 | EF 116 | EF 116 WW45 NH 402 | NH 105 ## Instructors:A. Taylan Cemgil ## TA:Ozlem Ozcan, ## Student TA## Announcement## BookMark Allen Weiss (3rd Edition is also OK) ## Course Logistics## Slides## C++ Reference MaterialIn this class, we won't follow a specific book for C++ but as reference material the following online resources may be useful: ## GradingMidterms : 20 + 20 Final : 26 Programming Projects : 26 (long) + 8 (short) (There will be 3 long projects and at least 2 short projects. All projects must be submitted.) Project Submission Information
All projects must be genuine, repeated cheatings will be prosecuted. ## Exam DatesMidterm 1 (7 Nov 2018, Wed, 13:00-15:00, ) Midterm 2 (5 Dec 2018, Wed, 13:00-15:00,) Final (TBA)
## PrerequisiteCMPE 160, or a Course with coverage of most of the following topics Object oriented programming concepts List implementations using arrays and objects, Doubly linked lists, Circular lists, Stack, and Queue Implementation General tree structure; Binary trees; AVL trees; B-Trees
## TopicsIntroduction to C/C++ Programming: Operator overloading, Pointers and reference operators, Shallow and Deep copy, Basic STL, Using the GNU compiler suite, Quick review of linked lists, stacks, queues, binary trees
Introduction to Algorithm analysis: Asymptotics, Landau (Big-Oh) notation , , ,
Priority Queues: Binary heaps, Application in Discrete Event Simulation
Sorting: Insertion Sort, Heap Sort, Merge Sort, Quicksort, Quick Find Lower bound for any comparison based sorting algoritm, contrast worst case and average case analysis, indirect sorting and in-place permutatons
Hashing Graph Basics: Definitions, Directed and undirected graphs, Representations: adjacency matrix, adjacency lists, Simple random graph generation and visualization (dotty)
Directed Acyclic Graphs, Topological Sort, Applications: digital logic circuit simulation/testing prerequisite relations
Searching on Graphs: Breadth-first traversal, Depth-first traversal Unweighted shortest path, Weighted graphs, Weighted shortest path, Dijkstra’s algorithm, Application in Erdös number calculation in a social network
Spanning Trees: Prim’s algorithm, Kruskal’s algorithm,
Disjoint set data structures, Union/Find algorithms Network flows: path augmentation, Applications in perfect matching and marriage problem
Dynamic programming: Recursions, Fibonacci numbers, matrix chain multiplication, maximum subsequence problem, shortest paths revisited
## Time Table
## Past Exams |