SEN2211 · Veri Yapıları ve Algoritmalar I

Data Structures and Algorithms I

Complexity analysis, linked lists, stacks, queues, recursion, searching and sorting.

Textbook: Data Structures & Problem Solving Using Java (Mark Allen Weiss)

  1. Week 1
    Introduction to Data Structures and Algorithms, Complexity Analysis
    • Complexity analysis: Big-O, Ω, ΘYou learn to count how many operations a piece of code performs and to write the result with Big-O. The basis of the “What is the running time?” questions that appear on the midterm every year.
  2. Week 2
    Introduction to Linked Lists
    • Singly linked listThe Node class, inserting at the front/back/middle, deletion and traversal. The source of the midterm questions “what is the final state of the list?” and “write this method”.
  3. Week 3
    Doubly Linked Lists, Ordered Linked Lists
    • Doubly linked, sorted and circular listsThe doubly linked list with a prev reference, the ordered list that keeps its elements sorted, and the circular list whose end is linked back to the start. The exam asks for reference update traces and the insertSorted method.
  4. Week 4
    Linked List Applications and Review
    • Linked list applications and reviewReversing a list, finding the middle, cycle detection, merging two sorted lists, and comparing lists with arrays. Most of the midterm's “write a method” questions come from these four algorithms.
  5. Week 5
    Stacks
    • Stack: with an array and with a linked listLIFO logic, push/pop/peek, two implementations with an array and a linked list, overflow and underflow. The exam asks for the state of the stack after a sequence of operations and for pop order questions.
  6. Week 6
    Stacks for Algebraic Operations
  7. Week 7
    Queues
    • Queue: with a circular array and with a linked listFIFO logic, enqueue/dequeue/peek, a circular buffer that prevents the array from drifting toward the start, and a linked queue with head/tail. The exam asks for the raw state of the array and the front/rear values after a sequence of operations.
  8. Week 8
    Queues II: Circular and Priority Queues
  9. Week 9
    Data Structure Classes in Java
    • Java's ready-made data structures: CollectionsArrayList, LinkedList, ArrayDeque, Stack, the Queue/Deque interfaces, Iterator and HashMap. The Java counterparts of the structures you wrote by hand, and which one to choose for which job. The exam has “what is printed” and structure selection questions.
  10. Week 10
    Recursion
    • RecursionThe base case and the recursive step, call stack traces, recursive methods on linked lists, and an introduction to backtracking. The exam has “what is printed”, call count, and recursive method writing questions.
  11. Week 11
    Recursive Complexity
    • Recursive complexity: recurrence relationsWriting the running time of a recursive method as a recurrence T(n), and solving it by unrolling, the recursion tree and the master theorem. The exam has “write the recurrence and give the Big-O” questions.
  12. Week 12
    Searching Algorithms
    • Search algorithms: linear, binary, interpolationLinear search, the loop and recursive forms of binary search, comparison counts, and the idea of interpolation search. The exam asks for a low/mid/high trace table and the worst-case number of comparisons.
  13. Week 13
    Sorting Algorithms I
    • Sorting I: bubble, selection, insertionThree basic O(n²) sorting algorithms, the state of the array after each pass, comparison and swap counts, and stability. The question “show the array after each pass” is almost guaranteed on the exam.
  14. Week 14
    Sorting Algorithms II
    • Sorting II: merge sort, quick sort, heap sortO(n log n) sorting by divide and conquer: the merge steps in merge sort, the partition trace in quick sort, an overview of heap sort, and a comparison table of all the sorts. Most of the final exam's sorting questions come from here.