Posts Tagged with Algorithms

week 6 covered topics:

  • HASHING: THE BASICS
  • UNIVERSAL HASHING
  • BLOOM FILTERS

Two programming assignments:

  • The goal is to implement a variant of the 2-SUM algorithm (covered in the Week 6 lecture on hash table applications)
  • The goal is to implement the "Median Maintenance" algorithm (covered in the Week 5 lecture on heap applications).

week 5 covered:

  • DIJKSTRA'S SHORTEST-PATH ALGORITHM
  • HEAPS
  • BALANCED BINARY SEARCH TREES

Programming assignment: In this programming problem you'll code up Dijkstra's shortest-path algorithm. The file contains an adjacency list representation of an undirected weighted graph with 200 vertices labeled 1 to 200. Each row consists of the node tuples that are adjacent to that particular vertex along with the length of that edge. Your task is to run Dijkstra's shortest-path algorithm on this graph, using 1 (the first vertex) as the source vertex, and to compute the shortest-path distances between 1 and every other vertex of the graph. If there is no path between a vertex v and vertex 1, we'll define the shortest-path distance between 1 and v to be 1000000.

week 4 covered:

  • GRAPH SEARCH AND CONNECTIVITY

Programming assignment: The file contains the edges of a directed graph. Vertices are labeled as positive integers from 1 to 875714. Your task is to code up the algorithm from the video lectures for computing strongly connected components (SCCs), and to run this algorithm on the given graph.

Week 3 covered:

  • PROBABILITY REVIEW
  • LINEAR-TIME SELECTION
  • GRAPHS AND THE CONTRACTION ALGORITHM

Programming assignment: The file contains the adjacency list representation of a simple undirected graph. Your task is to code up and run the randomized contraction algorithm for the min cut problem and use it on the above graph to compute the min cut.

Week1 topics:

  • INTRODUCTION
  • ASYMPTOTIC ANALYSIS
  • DIVIDE & CONQUER ALGORITHMS

Programming assignment: The file contains all of the 100,000 integers between 1 and 100,000 (inclusive) in some order, with no integer repeated. Your task is to compute the number of inversions in the file given, where the ith row of the file indicates the ith entry of an array.

Week covered:

  • THE MASTER METHOD
  • QUICKSORT - ALGORITHM
  • QUICKSORT - ANALYSIS

Programming assignment: The file contains all of the integers between 1 and 10,000 (inclusive, with no repeats) in unsorted order. Your task is to compute the total number of comparisons used to sort the given input file by QuickSort.