SI 413 Fall 2021 / Project


This is the archived website of SI 413 from the Fall 2021 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Project Phase 2

Overview

This is the main part of your project, and it consists of writing a slightly-more-substantial program in your language. There is no starter code here; you have to write the program "from scratch".

You must choose one of the problems listed below for your program to solve. Some of these problems are rather open-ended, meaning they aren't as precisely specified as most of the assignments and labs in this class. On each language's page, I've suggested which problems might work best for that language, but this is only a suggestion, not a hard-and-fast demand. This means first of all that you will need to clearly indicate, via a README.txt text file included with your submission, exactly what your program does (like which problem you are solving) and how it works at a high level. It also means that you have some more decisions to make. If you are at all unsure how to proceed, just ask! And keep in mind when deciding which problem to tackle and how to make your program work that:

It is your job in this phase to convince your instructor that you have learned the most important features and quirks of your programming language. Notice that I said "your job". This is actually explicitly worked into the grading scheme (see below). So for example if your Clojure program looks exactly like a Java program, and doesn't take advantage of or show off any of the aspects of Clojure itself, you will not receive a very high grade. If you choose a simple problem for Ruby, and therefore solve it in a 30-line program that anyone could write, your grade will reflect this lack of demonstrated expertise. If your brainfuck program consists 90% of copied code from the internet (even if it's all properly attributed/documented),... you get the idea. Again, this is not meant to be stressful but rather freeing - there is little chance of you missing some "stupid little detail" and being highly penalized for it. Again, if you're unsure or anxious, ask!

I recommend you start by looking at the list of suggested problems listed on your language's page: brainfuck, Piet, Dart, C Sharp, Rust, Elixir, Go, Prolog, Haskell, Red, Elm, Clojure, Nim, Ruby, Lua . Then come back here and look at the descriptions of those problems, keeping in mind the grading scheme below.

GOOD LUCK AND HAVE FUN!

Grading

Phase 2 counts as 50% of your total project grade. Remember that it is your responsibility to choose a problem and a way of solving that problem that shows off your mad skills in the language. Here's a break-down of how your grade will be computed:

  • 30%: Coding style. Remember that the "audience" of your code is someone who might not be that familiar with the language. This means you need to be extra careful to document clearly and extensively what is going on.
  • 30%: Appropriateness. What I mean by this is, how well does this program show off the features of your programming language and demonstrate that you have begun to master it? Does your program represent a significant accomplishment? It should represent more work than a lab, for example!
  • 40%: Correctness. Your program needs to work. It needs to solve the problem specified. It should behave as you describe in the README.txt file. Note: it will be very bad for you if, say, it doesn't compile!

The Problems

Remember, these are open ended so you can add or subtract aspects of the problem if that is more appropriate for your language. But if you do that, you should definitely run it by your instructor first! My suggestions of which problems might be best are listed on your language's page, so start there.

  1. Compiler
    Write a compiler, i.e., a program that translates from one language to another. There are actually (potentially) three different languages here: the language you compile from, the language you compile to, and the language the compiler itself is written in. Of course one of these must be the language of your topic! It's OK if, say, the compiled-from language is a somewhat simplified version of a popular, standard language. Make sure you check with your instructor on the choice of languages for this.
  2. Make
    Write your own version of the popular *nix utility make You definitely don't need to include all the features of the "real" make, but you should also add some new features. For example, if your language supports concurrency, you could have the program keep running in the background forever, automatically re-making any target whenever any of its prerequisites is changed. That would be neat-o!
  3. Matrix Calculator
    Write a program that can read in matrices (filled with integers), print them out, assign names to them, add, subtract, multiply, and any other operations you want to support. Many of your languages will have easy-to-find libraries that will do these computations for you - don't use them. You will have to define (and document!) the format of the input, as in, how to type in a matrix. Additional operations you might support are determinant, transpose, or adjoint. Ask if you need help in figuring out the math - that's not supposed to be the hard part!
  4. Image Creator
    You prompt for or otherwise read in a specification of an image, with things like circles, rectangles, lines, triangles, text, or anything else you like. Each "component" of the image must specify things like what its dimensions are and where it goes. The "where it goes" part might just be (x,y) coordinates or if you want to be fancy you could also allow it to be relative to another component. Then you produce a gif or bmp or png or ppm file with that image in it. You will have to define (and document!) the precise format of how the input is specified, of course.
  5. Game Scheduler
    In most organized sports with set schedules, many factors are taken into consideration in making a schedule for the season: rankings from the previous season, which division/conference each team is in, balancing home and away games, bye weeks, etc. For example, check out the way it's done in the NFL. Make a program to compute a valid, random schedule, given whatever the constraints are (and team names, and any other information) for the league. You might just make a valid NFL schedule, or you might need to be more general than that - it depends on your language and how you decide to do it.
  6. Hangman
    Write a program to play hangman. A word or phrase should be randomly selected from a (possibly huge) text file, and then the user gets to guess letters. If the letters are in the word, they get filled in, and otherwise a part of the man gets drawn. When the man is completely drawn... well hopefully you are familiar with this game. This could be console-based or fancier with GUIs.
  7. TODO list
    Write a "to-do" list program. This should (at a minimum) be able to read in new to-do items, and mark existing items as "done" in some kind of nice way. Other features that would be nice are persistence (save/load from a file so that exiting a program maintains the list), and concurrency (program can be running on two different terminals at the same time, and they are checking and updating some shared file, displaying updates immediately as they are entered).
  8. Vending Machine
    Make a program that simulates the actions of a vending machine. At the most basic level, there could be just one price, and the program waits for just a few different keystrokes indicating nickel, dime, or quarter, until that amount has been paid. Then the change is given (probably by printing out some indication of which coins it includes) and the program terminates. To make the program more sophisticated, you could have multiple items with different prices, allow more denominations of money (penny, 1/5/10/20 dollar bills, ...), or read some or all of these specifications from a text file.
  9. Game with hidden agenda
    Write a simple game (maybe hangman from above, or battleship, or tic tac toe, or...) that secretly does numerical computations in the background while the user is playing. For example, the program might be trying to factor a reasonably large number (e.g. for RSA cracking), or looking for a hash collision. These computations should be running in one or multiple threads without affecting the gameplay. The input and output from the numerical computations should come from text files in the directory, according to your specifications in the README.txt file. Importantly, when the game exits, the computations should halt immediately. (And if you're good, the computation should restart where it left off when you start the game again!)
  10. Frequency count
    Read in a text file and count, record, and finally display the frequency of each letter, or each digit, or each word that appears. If you want to be fancier, count the frequency of words, stripping away all punctuation and ignoring whitespace and capitalization, and sort the results to only display the 50 most popular words, along with their frequencies. You had better count words instead of letters if your language is in this list! A possible extension would be to count frequencies in multiple files simultaneously and only display the accumulated results when all counts finish.
  11. Guess the language
    Like the frequency count, but in this problem you want to figure out what (human) language the input is written in. You compare each word in the input with the words in a bunch of plain-text dictionary files, one dictionary for each language. For EVERY dictionary that you find the word in, you increase the "count" for that language. At the end, you return the name of the language with the highest count, that is, the (human) language that contained the most words that were input. To help you out, there are some languages' dictionaries in the folder /courses/roche/413/dicts.
  12. Find the missing digits
    I remember some math problems from grade school where you get a long-number addition or multiplication problem where some of the digits are x's, like
      4x89x
    + 32xx7
    -------
      7x150
    
    and you have to figure out a possible setting for all of the "x" digits that makes the math work out correctly. (Notice that each "x" can be a different digit!) Write a program to solve this problem, by taking the three numbers as input (with x's in them), and the choice of operation (+, -, or *). There may be many solutions to a single problem; you decide whether your program will just produce one of them, or all of them, or give you one and ask if you want to see more, etc. This isn't grade school so your program should be able to handle some big numbers!
  13. Sports Ticker
    Read a list of sports teams, or leagues, or maybe even specific games, and then make an interface that continually gets updates for the relevant games and displays the score updates on the screen. Depending on your language, the output could just be in the terminal, or it could be some kind of GUI. You will have to find a (free) API to use; mysportsfeeds seems like a good option since you can get a free API key for non-commercial use.
  14. Rock, Paper, Scissors
    Write a program that will play the Rock, Paper, Scissors game against a human opponent. A good "strategy" for your computer player might be to count the frequency of which move the human has made most often, and then choose the counter-move to maximize your computer strategy. The game should keep track of the total win-loss-tie numbers as the game progresses.
    There are many small variations you could do here, depending on how complicated you want your program to be:
    • Make the computer AI strategy more sophisticated
    • Introduce a configuration file which would allow variations such as Rock-paper-scissors-lizard-Spock.
    • Make it a multi-player network game
    • ...
  15. Music Maker
    Make a program which reads in a musical "score" in the format of your making, and then produces a simple wav file with an audio rendition of that score. The exact format of your scores should be specified in your README, but a good starting point would be a list of note-duration pairs. For example, here's the first line of Anchors Aweigh in D major (I'm using R for a rest):
      D 2
      F# 1
      A 1
      B 1.5
      F# .5
      B 1.5
      R .5
      D 2
      E 1
      A 1
      D 3
      R 1
      
    You'll have to figure out how to decide tempo, distinguish between octaves, etc. If you want to get fancy, you can try having multiple melody lines and different instrument patches, but I'd start with the basics here: one melody line and a pure pitch per note using a square wave or sine waveform. The wav format has a number of options but if you stick to, say, 8-bit uncompressed mono, it should be not too hard to get started.
  16. ???
    If you have a better idea for a problem to solve in your language, I'm open to it. Of course you should run it by your instructor first! But it doesn't need to be a formal proposal or anything like that. A short description like for any of the other problems above would be fine.

Submission

Unless otherwise indicated, I will compile/run your program the same was as I did in Phase 1 of the project, as specified on your language's page. You should submit all the code, as well as a README.txt file describing what problem you solved and how, using the normal submit program that we use in labs, as "413 proj 02". Be sure to check the list of files that actually get submitted in case there are any missing. And as always, submit early and submit often!