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 2017

250.01 WW67 Th2 BMA2 BMA2 BMA2
250.02 WW67 TH3 NH105 NH105 BMA3
PS Th3

Instructors:

Levent Akin
A. Taylan Cemgil
For contact details and further information see the web: http://www.cmpe.boun.edu.tr/~cemgil/

TA:

Ozlem Ozcan, Alper Alimoglu

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

PDF

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 (8 Nov 2016, Wed, 14:00-16:00, )

  • Midterm 2 (6 Dec 2016, Wed, 14:00-16: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 Theta, O, Omega, o

  • 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 21/09/17 C++ 1. chapter
2 28/09/17 C++ 1. chapter/algorithm Analysis
3 05/10/17 Priority Queues
4 12/10/17 Priority Queues
5 19/10/17 Sorting (Insertion, quick, merge)
6 26/10/17 Sorting (Insertion, quick, merge) + Hashing
7 08/11/17 Midterm I
8 09/11/17 Graph Algorithms (Graph representations, Topological sort)
9 16/11/17 Shortest path, breadth first search, Dijkstra,
10 23/11/17 Spanning Tree (Prim, Disjoint Set, Kruskal)
11 30/11/17 Network flow, depth first search
12 06/12/17 Midterm II
13 14/12/17 Dynamic programming

Past Exams

  1. exams/2010fall-cmpe250-final.pdf

  2. exams/2010fall-cmpe250-midterm1.pdf

  3. exams/2010fall-cmpe250-midterm2.pdf

  4. exams/2011fall-cmpe250-final.pdf

  5. exams/2011fall-cmpe250-midterm1.pdf

  6. exams/2011fall-cmpe250-midterm2.pdf

  7. exams/2011spring-cmpe250-final.pdf

  8. exams/2011spring-cmpe250-midterm1.pdf

  9. exams/2011spring-cmpe250-midterm2.pdf

  10. exams/2012fall-cmpe250-final.pdf

  11. exams/2012fall-cmpe250-midterm1.pdf

  12. exams/2012fall-cmpe250-midterm2.pdf

  13. exams/2012spring-cmpe250-final.pdf

  14. exams/2012spring-cmpe250-midterm1.pdf

  15. exams/2012spring-cmpe250-midterm2.pdf

  16. exams/2013spring-cmpe250-midterm1.pdf

  17. exams/2013spring-cmpe250-midterm2.pdf

  18. exams/2014fall-cmpe250-final.pdf

  19. exams/2014fall-cmpe250-midterm1.pdf

  20. exams/2014fall-cmpe250-midterm2.pdf