CS 512 FINAL PROJECT
General Information.
Find below some important information regarding the group projects that must be submitted
this semester.
Stages.
Stage 1: Project proposal < Due on Monday November 23, at 11:55 pm > Prepare a
description of your group project.
The project proposal will be reviewed by the Grader and feedback will be given to you by Friday
November 27.
Stage 2 < Due on Tuesday December 15, at 11:55 pm > The deliverables for this stage include:
• Report including: 1) High level description (pseudocode) of your project, 2) how data was
transformed and used, 3) overall time and space complexity,
• Demo of a working prototype (ppt file).
• Source code of your project and video (if appropriate)
Suggested Approach for a successful project.
In order to create a good and feasible description of your GROUP PROJECT we suggest you at
every step to Make sure you divide the labor fairly in *Programming, *Data
Collection, and *Results Reporting and Documentation.
Discuss with your group members what type of project you want to complete by asking the
following questions:
a. *Visualization of a known algorithm, *Implementation of an algorithm not covered in
class , *Novel Application of a known Algorithm, *New Algorithm for a known application
b. What kind of data you would like to work with.
c. What is the input format for the data and what is the size of the data. Does it fit in a typical
desktop? or do you need a special server for it? is it data at rest or is it streaming data?
d. Formulate three typical and specific questions you would like to answer about the data.
e. How are the answers presented to a user of your application?
f. What are the algorithms you will be using? What is their complexity as a function of the
input size?
g. Do you have access to implementation of the algorithms? Language(s) to be used
h. What is novel about your project? Is the Data? Is the Algorithm? Is the Implementation ?
i. Is your project feasible? i.e. you will need to demo a working prototype 4-5 weeks from now .
j. Match the skill sets of the group members to each of the tasks at hand in a fair manner.
Suggested Topics.
Useful Languages to know: C/C++, Java, JavaScript, Python (or Perl)
Goal: To become exposed to some of the current major algorithm classes that have become or are
becoming predominant in applications.
Projects can be chosen from one of the following areas:
a. Deterministic Algorithm Animation and Algorithm Snippets
To have a better idea of the quality expected from your Algorithms Snippets projects, please
take a look at the following YouTube channel containing videos produced by Professor Sesh
Venugopal (one of our faculty members).
https://www.youtube.com/channel/UC3QLHt6mHfmg4x_h2am7ecg
The expectation is that you will work on graduate class algorithms (i.e. a bit more advanced than
these ones in these videos).
• Expected Outcomes: Instructional Videos or Pseudo Code Driven Animation
• Suggested Topics: From Sec 1.3, 1.4, and 1.5 of DVP:
• Primality, Cryptography, Universal Hashing
• Max Flow-Linear Programming- Planarity –
• Graph Decompositions – Graph Drawing –
• NP-Completeness,
• Clustering.
b. Advanced Algorithm Sampler
• Expected Outcome: Digital Literature Survey and Search Interface Prototype
• Suggested Topics: Same as those listed in item a. above but in
• External Memory, Data Streaming, or Parallel and Distributed settings.
c. Dealing with NP-Completeness
• Expected Outcome: Digital Literature Survey and Search Interface Prototype
• Suggested Topics: Approximation Algorithms, Fixed Parameter Tractability.
d. Adaptive Graph Mining
• Expected Outcome: Exploratory Data Driven Prototype (Adaptive Navigation and
Summarization).
e. Massive Algorithmics
• Expected Outcome: Library of Scalable Algorithms and Two Sample Applications.
• Suggested Topics: Personalized Page Rank, Heavy Hitters, Near Neighbors Search, Similarity
Search, Recommendation Systems, Deep Learning.
f. Scalable Algorithms Infrastructure
• Expected Outcome: make Hadoop and MapReduce based environments operational.
• Suggested References: BigTable, Dynamo, NoSQL, and Mongo.