COMP 118, Fall 2023
This test will consist of three parts:
- A signup for when you will be taking the moodle portion. Link
Due by Wed. Dec 6pm. - A timed moodle based test (2 hours). (60%) Link
- A Kattis contest (5 days).(40%) Python Link, C++ Link
The moodle test
The Moodle link is here: Moodle test
This will be much like the quizzes, only longer. You can decide to take it:
- Tuesday Dec 12, 8-5pm: On your own. I will not be on campus, but will be avialable via email for questions. Once you start teh exam you have two hours to complete. You can not use any other resources during this portion.
- Thursday Dec 14, 6:30pm-8:30pm. This is in person in Hayes 311.
- Friday Dec 15, 8:30-10:30. This is in Pierce 09.
Use this FORM to let me know when you will be taking the exam. Note that I can only have up to 25 students per time on Thursday and Friday, and it will be first come first serve based on the signup form. If too many pick a date, the later ones may be reassigned.
The Kattis Contests
There will be 2 Kattis contests. One will be for Python solutions, the other for C++ solutions. In each there are 8 problems, the same problems.
You will be required to solve a total of 12 problems for full credit. You choose which languages, but of course to solve 12 you will need at least 8 of one, and 4 of another.
If you solve more then 12 I will give extra credit toward the rest of the exam.
Below are the links:
Hints:
There will be hints for how to solve the Kattis problems here. Since I’m mainly interested in how you can code, I will give you some algorithm hints on some of the harder problems.
Magic Trick Problem
For this you could have a nested loop. The outer loop cycles through all the characters, and the inner loop also cycles through all the characters. Inside the loops you can check to see if there is ever a duplication of any character. There are other ways to approach this as well.
Death Knight Problem
Really needs no help!
The Grand Adventure Problem
The trick with this one is to use a list or array as a “stack”. Imagine a stack of papers. You put something on the top the stack by “appending” it to the end of an array, and you remove something from the top by “popping” from the stack.
What you will need to do is push an item (money, incense or gem) on the top of the stack. When you encounter a trade, jeweler or banker, you can only proceed if there is the correct item on the top of the stack (end of the list or array). If there is a match, you can pop the item off the stack of items.
Heimavinna Problem
This problem is scaled. There are 3 levels of completeness in the table, and you can get partial or total credit.
The hint here is to use the split in python. You can split with “;” to break up the initial line, then split with “-” to break up ranges.
For C++ you must isolate the numbers using the substr method. You can use the “stoi” function to convert a string to an integer:
string str1 = “45”;
int myint1 = stoi(str1);
Runlengthencodingrun
This also requires the converting of numbers in a string to integers. Use the hint above.
Hay Points Problem
The trick here is to use a dictionary for python, and a map for C++. Of course you need to parse the input, but we have done a lot of that.
If you use a nested loop to search for a match it will take too long for long cases, and you will get a time exceeded.
Army Strength Problem
For this one you will need to parse arbitrary length input of ints. Here is a line of code that does that:
gs=[int(x) for x in input().split()]
It is also useful to sort the armies by strength.
The idea here is that you run through a loop, and have the weakest monster on each side fight. The stronger one lives, and the weaker dies. If it is a tie, then MechaGodzilla always loses. When one side runs out of monsters, the other side wins.
Engineering English Problem
Use a dictionary or a C++ map!