CMPE 250 Data Structures and Algorithms
The 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 2018
250 WThTh634 NH 105 | EF 116 | EF 116 WW45 NH 402 | NH 105
Instructors:
A. Taylan Cemgil
For contact details and further information see the web: http://www.cmpe.boun.edu.tr/~cemgil/
TA:
Ozlem Ozcan,
Student TA
Announcement
Book
Mark Allen Weiss
Data Structures and Algorithm Analysis in C++, Fourth Edition
ISBN-13: 9780132847377
(3rd Edition is also OK)
Course Logistics
Slides
C++ Reference Material
In this class, we won't follow a specific book for C++ but as reference material the following online resources may be useful:
Grading
Midterms : 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 Dates
Midterm 1 (7 Nov 2018, Wed, 13:00-15:00, )
Midterm 2 (5 Dec 2018, Wed, 13:00-15:00,)
Final (TBA)
Prerequisite
CMPE 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
Topics
Introduction 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
| 1 | 20/09/17 | C++ 1. chapter |
| 2 | 27/09/17 | C++ 1. chapter/algorithm Analysis |
| 3 | 04/10/17 | Priority Queues |
| 4 | 11/10/17 | Priority Queues |
| 5 | 18/10/17 | Sorting (Insertion, quick, merge) |
| 6 | 25/10/17 | Sorting (Insertion, quick, merge) + Hashing |
| 7 | 07/11/17 | Midterm I |
| 8 | 08/11/17 | Graph Algorithms (Graph representations, Topological sort) |
| 9 | 15/11/17 | Shortest path, breadth first search, Dijkstra, |
| 10 | 22/11/17 | Spanning Tree (Prim, Disjoint Set, Kruskal) |
| 11 | 29/11/17 | Network flow, depth first search |
| 12 | 05/12/17 | Midterm II |
| 13 | 13/12/17 | Dynamic programming |