We all use production quality software comprising millions of lines of code in our daily lives, be it the Android or IoS operating systems or the Facebook or Twitter social networking programs. However, most of us write tens to at max hundred lines of code, that sometimes fail to run on our own computers. This course is a self driven attempt to make our programming skills a bit less clumsy. Thinking carefully (a) how software should be organized into classes and functions to create better abstractions, (b) what data structures and parallelization can improve space-time efficiencies so that our code runs faster and uses less hardware resources like RAM, (c) how the different source and header files should be compiled and cleaned through Makefiles to remember dependencies, (d) how to use gdb instead of scattering printf-s all over the code to debug issues, (e) how to stop mailing our team-mates code versions and then not finding the code to upload in moodle 5 minutes before deadline by appropriate version control in git etc., are more important goals in this course, than just being functionally correct in the tasks.
What we will be doing
There will be three tasks and one end-sem hackathon. All three tasks should be done in groups of two. The hackathon will be an individual effort, mostly to see if everyone contributed equally through the semester and learned enough.
The first two tasks need to be implemented in C++ and the third in any programming language of your choice. The first task is mostly a warm up exercise to let you learn some new tools - Makefile, gdb, gnuplot, latex etc. It will be broken into four sub-tasks each a week long. The shorter evaluation cycles of a week will allow us to gauge your strengths and weaknesses better and see who among you might benefit from some discussions with me or the TAs. The second and third tasks will be given as a whole with over a month's time as deadline. (a) How to break these longer tasks into sub-tasks to make gradual progress, (b) how to keep working on it though the deadline is somewhat far to reduce last minute surprises, will need careful project planning and self discipline. The hackathon will be a 1-2 days event after the majors are done, where you will complete task 3.
Tasks will be released on this webpage with submission links on moodle. Tasks need to be done on Linux machines. Though there is no lecture component in the course, the whole class will meet me and the TAs at some intermediate times. The time and venue will be communicated over email. The meetings (3-4 of them over the semester) will be about an hour long. We will discuss common issues we are finding in your submissions, the upcoming tasks etc. Students can ask any doubt that they might have in prior submissions or upcoming tasks.
Things to care about
Typically this is called the honour code for any course. Read as much as you want online resources and discuss among friends to understand the concepts. But the implementations, graphs and reports that you submit should be your own. No copy pasting of code from the internet or across groups. The reason is simple. We all will be professional programmers at some point in our lives with a Computer Science major or minor degree. Will we trust a civil engineer to build our bridges, if we know he copied all through his engineering projects? Will we trust a doctor to prescribe medicines, if we know that he passed exams by copying from cheatsheets? Will we trust a chemist to create those medicines if she copied all the chemical equations? The professional ethics that we expect from our politicians, doctors, civil engineers, chemists etc. should be the same as what we expect from ourselves. Cheating is insulting our own creativity and intellect.
[1] Task1: Create a small image processing library
Task release date Jan 8, final submission deadline Feb 5 with three intermediate deadlines on Jan 15, Jan 22 and Jan 29.
(a) Subtask1: Warming up to compiling and debugging some C++ functions: Jan 8- Jan 15
Implement the following functions using 32 bit float as datatype.
convolution of a square input matrix and a square kernel, both matrices of any size and the kernel smaller than the input
with and without input padding to maintain or reduce the size of the input matrix
implement the function both as convolution and as matrix multiplication
non-linear activations of an input matrix of any size with relu and tanh functions on individual matrix elements.
subsampling of square input matrices of any size with max pooling and average pooling functions
We will test each function with different inputs in text files.
vectors stored as single values in each line of the file
matrices stored in column major order in each line of the file
We will create an assignment in moodle. Any one of the two team members upload a single tar file there with name entrynum1_entrynum2_ass1.tar.gz. It should contain your source code, Makefile and a readme describing the names of the different functions and how to call them from command line. E.g. command line ./yourcode.out convolution_withpadding_matrixmult padsize matrix1.txt matrix1_numrows matrix2.txt matrix2_numrows. A wrong command line should print the appropriate help.
(b) Subtask2: Code performance, learning plotting through scripts: Jan 15 - Jan 22
Accelerate matrix multiplication speed for convolution in your previous implementation with
linear algebra libraries mkl and openblas. Are these libraries faster than your own C++ matrix multiplication?
pthreads. Check for correct computation of the matrix multiplication results and synchronization issues with multiple threads if any.
Measure mean and standard deviation of latencies of the three implementations (mkl, openblas and your pthread implementation) over different matrix sizes and plot a box plot with error bars using gnuplot. Can your own pthread based implementation match openblas, mkl speeds?
In addition to previously mentioned command line ./yourcode.out convolution_matrixmult matrix1.txt matrix1_numrows matrix2.txt matrix2_numrows, there will be one additional command line option (mkl or oprnblas or pthread), to use the appropriate implementation. Again, we will test with different matrices. The outputs should be same across the different implementations (accurate) and the speed differences should match what you present in your graph.
We will create an assignment in moodle. Any one of the two team members upload a single tar file there with filename entrynum1_entrynum2_ass2.tar.gz. It should contain your source code, Makefile, gnuplot script, plot in eps and png formats and a readme describing the names of the different functions and how to call them from command line.
(c) Subtask3: Hierarchical code design, learning latex documentation: Jan 22 - Jan 29
Implement LeNet (paper, software architecture) inference for MNIST digit recognition stitching together the functions you have written so far. You will be given pre-trained weights and bias values and some sample images to test your implementation.
We will test your code with any image from the MNIST dataset. In addition to source code, you will also have to submit a small report in latex.
(d) Subtask4: Creating libraries with appropriate APIs: Jan 29 - Feb 5
Create your own image processing library with different api-s that we can call from a cpp program.
API2: given an MNIST image, output top 3 digits with highest softmax probabilities
[2] Task2: Write a simulator for an Indian road traffic intersection
This task needs you to write a C++ simulator for Indian road traffic intersection. You need to simulate only one road in the intersection. You do NOT need to simulate a bi-directional road where traffic flows in both directions. You also do NOT need to simulate all roads in the three or four way intersection. You need to simulate one road, covering one direction of traffic flow, facing a traffic signal. I am including some images below as the intended scenario.
The images above shows sample video frames from a fish-eye lens traffic camera in Noida. The camera looks from the traffic signal towards the incoming traffic flow. See how vehicles gradually come towards the signal.
The images above shows sample video frames from another traffic camera in Noida. This camera looks from the traffic signal towards the outgoing traffic flow. See how vehicles gradually move away from the signal, when the signal turns green.
You need to create a configuration file that contains all details of your simulation -- what kind of vehicles you are simulating (bus, car, two-wheelers, three-wheelers, trucks etc.), what properties your vehicles have (length, width, speed, acceleration, braking, color, lane change frequency etc.), what other things you simulate (road, traffic signals etc.), the properties of those other things (length and width of roads, signal colors etc.), time step by which your simulation moves forward (discrete simulation is fine), at what points of time what events occur (vehicles enter the road, signal changes color, vehicles leave the road, vehicles change lanes to overtake etc.).....
Your C++ code should process the configuration file and run the simulation. Start with the visualization of the simulation output on the terminal. Then have the same output visualized with OpenGL. Even in OpenGL, start with rectangles of different lengths and widths as vehicles, and make the visualization more fancy if you can.
A simple configuration file and its terminal output are at config.ini and out.txt. Your configuration file can look completely different, your C++ code should understand it. And the more you make it look like Indian driving (acceleration and brakes, lane changing and overtaking of larger vehicles by smaller ones), the more realistic it will be.
The first deadline for this was on Mar 17. On Mar 23, we are requesting a feature extension. The least changes your configuration file and C++ code needs to have, to support this extension, the more marks you will get. So think about scalable design, object oriented programming, minimum hard coding all through. As with Task1, there will be partial marking. So keep making progress on different fronts, if something in particular seems tricky.
Feature requested on Mar 23: Realistic lane change behavior for Indian traffic. Start with configurations where two or more larger vehicles are already standing near a red signal. Now simulate the movement of smaller vehicles through gaps between those larger vehicles, so that the motorbikes go and stand on the zebra ahead of everyone else and auto-rickshaws are stuck in odd angles between two cars or a car and a bus. Simulate for both command line display as well as OpenGL. Deadline is Mar 31.
[3] Task3: Design and implement a game highlighting a cause you care about
Computer games or web games or mobile games or AR/VR games form a multi-billion dollar industry. To harness this craze for gaming for social or environmental causes, there have been some efforts on games for social good or games with purpose example1, example2, example3.
In this task you will design and implement your own game highlighting a cause that you care about. You need to make a lot more design decisions, compared to the first two tasks.
What is the cause that you care about?
The 130+ odd students in COP290 class are a heterogeneous bunch, based on what bothers them about the current world (other than too many courses and assignment load, the next foreign university or industry internship, bad mess food etc. that bug you everyday). It might be mental health issues in teens and adolescents that you or some of your friends face ( e.g. mentalhealth1, mentalhealth2, mentalhealth3, mentalhealth4, mentalhealth5, mentalhealth6), elderly issues that your grandparents are facing and your parents might face in future (loneliness after spouse's death or lack of tech savyness but need to interact with children staying away from home (e.g. elderlies), environmental sustainability issues that are already causing havoc around the world (climate change, pollution related health risks - e.g. climate1, climate2, climate3, climate4), non-accountability of politicians, too much religious tolerance or intolerance ........ things which bother you can be very different. Your first task is to decide what cause you highlight in your game and convince your team-mate who might feel deeply about something else.
How to gamify the cause that you care about?
Once you and your team-mate are on the same platform about the cause, this will be the second design decision. You deeply care about something but you don't seem to find a way to directly help that cause with a game. Even raising awareness about a cause that you care about, helps the cause. So can your game subtly share more information about the cause? This part of the design is most crucial - so that your game and your cause do not feel too disconnected. If you find absolutely no way to gamify the cause you care most about, choose a different cause that is easier to gamify. But realize that these are the kind of compromises we keep making in life, taking an easy route out, and the problems we care most about remain unaddressed. Even if you can gamilfy your cause, the levels in the games, the scoring options for the players, the data and states that need to be maintained or communicated across players or a player and a server, need careful thinking.
What is your target population who will play your game?
Hand-in-hand with your cause, will be the target game population. Children, teen-agers, teen to mid-age or elderlies, who would play your game? The design should be appropriate - not too much violence for children, slower and bigger UI elements for elderlies..... If it is targeted towards CS undergrads in one of the top CS schools in the country, then you can design a completely geeky command line game and test it with your classmates. For any other population, some serious thought on UI design will be needed.
Single player vs. multi-player?
Multi-player games might be more fun as natural competitiveness of humans creates easier incentives to continue playing. However, if your game is for a shy adolescent coping with anxiety issues, he or she might not be comfortable to share those insecurities with another person. Or maybe its actually the opposite, he is trying to reach out to someone and a two or multi-player game is a perfect way for him to make the other players aware of his mental state. Think carefully of the appropriate modality. Or have both versions in the game, where people can choose between the single and multi-player versions.
What programming language to use?
C++ or Java or Python or Django or Android or .......? Will this be a mobile game or a web game or .... ? Will it be a 2D game or a 3D game? Play to the strength of your team, depending on what you are most comfortable with. Think whether nice interactive UI is more useful for you or UI elements can be minimal but computation or graphics rendering speed is of essence. We cannot give you any hardware support like Android or IoS phones or AR/VR gears, as the class size is large, but feel free to use any specialized hardware that you might already have. Or stick to your laptops, that's perfectly good.
Important Dates
May 4: Upload a presentation (maximum 15 slides):
a. describing the above design choices, and additional ones that are relevant for you.
b. Also describe the implementation highlights: the UI (put some screenshots or a small screencast), whatever storage and communication elements are needed, whether you used some existing framework(s) or built everything from scratch.
c. Describe a set of metrics by which we should evaluate your particular game design and implementation. Some of you might have very sophisticated game logic, some might have some non-trivial scoring mechanisms, some might have the most dazzling UI, some others have zero latency and great responsiveness ...... list all metrics that you think matter for your game, and say what trade-offs you had to do among those metrics (possibly due to lack of time, you couldn't optimize everything and traded some metrics for others).
d. The last slide should have your git repo link (not public). We will check the commit history, and match it with the implementation description in your presentation.
May 7: Finish the implementation, give finishing touches, and make at least 4 individuals for single player/ 2 pairs for 2 player / 4 people for a multiplayer game, play your game. Take videos of them playing (and potentially praising/cursing you). Bring the videos for evaluation. Final evaluations will be May 7 post lunch with individual TAs (time will be communicated later).
Git is mandatory
From May 4 onwards, we will keep checking your repos for commits. Don't make the repo public, but share with me and the TAs (we will send our Git usernames over email).