Difference between revisions of "Programming Practice"

From Computer Science
Jump to: navigation, search
(Sites with Problems)
(Algorithm Techniques)
 
(8 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
This page is meant to get you started working on programming problems that are similar to ones you will see in programming contests and job interviews.
 
This page is meant to get you started working on programming problems that are similar to ones you will see in programming contests and job interviews.
 +
 +
For the spring of 2021 we will meet Mondays at 9pm on Zoom to go through some of the problems.  See your email for the Zoom link.
 +
 +
We have a group on MS Teams to communicate and store files.  The link to request to join is [https://teams.microsoft.com/l/team/19%3a98d801f44cd44f1397f4e80f411dd110%40thread.tacv2/conversations?groupId=447ffad4-966c-4374-9614-62390f5715a0&tenantId=3eeabe39-6b1c-4f95-ae68-2fab18085f8d here].
  
 
= Sites with Problems =  
 
= Sites with Problems =  
'''[[Hackerrank.com]]'''
+
Each of these sites requires you to create an account to submit your potential solutions, and each is free to use.  You will often want to debug your code on your own computer and just submit your solutions on the site when you think your code is correct (at least gives the correct answer on some test input).
 +
 
 +
* '''[https://hackerrank.com Hackerrank]'''
 +
* '''[https://open.Kattis.com Open Kattis]'''
 +
 
 +
= Getting Started =
 +
* Create an account on whatever site you are taking a problem from.
 +
* Read the problem carefully.  Make sure you understand the sample input and sample output given for the problem.
 +
* Figure out an algorithm that will solve the problem.  You should try possible algorithms on paper using the sample input and sample output given.  If you cannot solve the sample input and sample output then there is no point writing a program that won't be correct.
 +
* When you think you have an algorithm that will work, write the code.  Test the code on the sample input and sample output given.  Make sure it gives the right answer.
 +
* After you have code giving the right answer on the sample input/output, submit it on the site.  If it is marked as incorrect, carefully read the problem again, carefully look your code again - there must be some case you are not handling properly.
  
'''Open.Kattis.com'''
+
Some problems to solve to get started. These are fairly easy and should get you familiar with submitting problems.
 +
* Hackerrank: [https://www.hackerrank.com/challenges/30-hello-world/problem hello world], [https://www.hackerrank.com/challenges/30-loops/problem loops], [https://www.hackerrank.com/challenges/30-arrays/problem arrays], [https://www.hackerrank.com/challenges/30-recursion/problem recursion], [https://www.hackerrank.com/challenges/30-sorting/problem sorting]
  
 
= Why Your Program is Wrong =
 
= Why Your Program is Wrong =
Line 17: Line 32:
 
The following are some of the most common algorithms/techniques that you will see with these problems.
 
The following are some of the most common algorithms/techniques that you will see with these problems.
  
# '''Simulation''' - the problem gives rules to be used to run a simulation, and you need to run the simulation until a certain point and output the result.
+
# '''Simulation''' - the problem gives rules to be used to run a simulation, and you need to run the simulation until a certain point and output the result.  Here are a few non-trivial ones (but not toooo hard) to try out - [https://www.hackerrank.com/challenges/an-interesting-game-1/problem Gaming Array], [https://www.hackerrank.com/challenges/new-year-chaos/problem New Year Chaos].  Note - sometimes there are additional tricks needed to make the program faster, but the first step is to just follow the rules to keep track of things and see what happens in the end.
  
 
# '''Brute force'''
 
# '''Brute force'''

Latest revision as of 00:36, 9 March 2021

This page is meant to get you started working on programming problems that are similar to ones you will see in programming contests and job interviews.

For the spring of 2021 we will meet Mondays at 9pm on Zoom to go through some of the problems. See your email for the Zoom link.

We have a group on MS Teams to communicate and store files. The link to request to join is here.

Sites with Problems

Each of these sites requires you to create an account to submit your potential solutions, and each is free to use. You will often want to debug your code on your own computer and just submit your solutions on the site when you think your code is correct (at least gives the correct answer on some test input).

Getting Started

  • Create an account on whatever site you are taking a problem from.
  • Read the problem carefully. Make sure you understand the sample input and sample output given for the problem.
  • Figure out an algorithm that will solve the problem. You should try possible algorithms on paper using the sample input and sample output given. If you cannot solve the sample input and sample output then there is no point writing a program that won't be correct.
  • When you think you have an algorithm that will work, write the code. Test the code on the sample input and sample output given. Make sure it gives the right answer.
  • After you have code giving the right answer on the sample input/output, submit it on the site. If it is marked as incorrect, carefully read the problem again, carefully look your code again - there must be some case you are not handling properly.

Some problems to solve to get started. These are fairly easy and should get you familiar with submitting problems.

Why Your Program is Wrong

Automatically Checked

Programming contests are normally checked by scripts that run your program and check whether your input is exactly the same as the model solution. If the correct output is "Hello World!", your program would be incorrect if it output "Hello World." or "hello world!". If the problem asks for an integer then make sure to output an integer (not a floating point number). So you need to pay careful attention to what the problem asks for in terms of output.

Run time

Some contest problems are fairly easy to solve with an inefficient program, but the real work is figuring out how to make your program faster. Oftentimes, your program needs to finish in around 1-5 seconds to be fast enough. For a C program, a single loop that goes through around 100 million iterations might be okay. For a Python program, a single loop that goes through 1 million iterations might be okay. If you have nested looped, you should count how many times the innermost part runs - two nested loops that each go 1 to 1000 will end up running the innermost code 1 million times.

Algorithm Techniques

The following are some of the most common algorithms/techniques that you will see with these problems.

  1. Simulation - the problem gives rules to be used to run a simulation, and you need to run the simulation until a certain point and output the result. Here are a few non-trivial ones (but not toooo hard) to try out - Gaming Array, New Year Chaos. Note - sometimes there are additional tricks needed to make the program faster, but the first step is to just follow the rules to keep track of things and see what happens in the end.
  1. Brute force
  1. Dynamic programming
  1. Graph problems
  1. Greedy
  1. Sorting
  1. Math tricks