A Prologue to Programming Ideas and OI-programming

Presentation Transcript

An Introduction to Programming Concepts and OI-programming … from unique hypothesis to messy traps…

Objectives Today Introduction to the idea of " Algorithms " Introduction to intricacy " Philosophy " of OI rivalries " OI-style " programming

What is an Algorithm? From Wikipedia: A calculation is a limited arrangement of all around characterized directions for fulfilling some errand which, given an underlying state, will end in a comparing conspicuous end-state. (what does that mean?) Usually, a calculation tackles a " issue " . Illustrations Insertion sort Binary Search A calculation does not need to be a PC program! Consider other conceivable calculations, in actuality

" Problem " s Usually an arrangement of all around characterized inputs and comparing yields Example: the sorting issue: Input: a rundown of numbers Output: a sorted rundown of numbers There can be numerous calculations that takes care of a similar issue e.g. Bubble Sort, Bogosort

Examples of calculations Sorting calculations Graph calculations – Djikstra, Warshall-floyd, Bellman-Ford, Prims, Kruskal Tree-Search calculations – BFS, DFS Linear Searching Algorithms

Examples of Techniques in Designing Algorithms Recursion Dynamic programming Greedy Divide and vanquish Branch and bound (the above may have covers)

Using and Creating Algorithms " It is science. You can determine them. " It is workmanship. We have no real way to show you! " Why concentrate on calculations? To tackle issues that can be specifically illuminated by existing calculations To take care of issues that can be settled by joining calculations To get emotions and motivations on the best way to plan new calculations

Related Issues Proving accuracy of calculations Can be extremely troublesome Disproving is less demanding  All you need is only one counterexample

Complexity An estimation to the runtime and memory necessity of a program. We wear " t truly think about the correct numbers (why?) In many cases, we concern runtime just Note that there are " best-case " , " normal case " , and " most pessimistic scenario " many-sided quality Usually we take a gander at the very least case just We need to know how well a calculation " scales up " (i.e. at the point when there is an extensive info). Why?

Complexity (cont " d) Here " s why:

Quasi-Formal Definition of Big-O (you require not recall these) We say f(x) is in O(g(x)) if and just if there exist numbers x 0 and M to such an extent that |f(x)| ≤ M |g(x)| for x > x 0

Example 1 – Bubble sort For i := 1 to n do For j := i downto 2 do if a[j] > a[j-1] then swap(a[j], a[j-1]); Time Complexity? O(n 2 ) How about memory?

Example 2 – Insertion Sort Quick prologue to addition sort (you will take in more in the looking and sorting preparing): [] 4 3 1 5 2 [4] 3 1 5 2 [3 4] 1 5 2 [1 3 4] 5 2 [1 3 4 5] 2 [1 2 3 4 5] Time Complexity = ?

Applications Usually, the time many-sided quality of the calculation gives us an unpleasant estimation of the genuine run time. O(n) for extensive N O(n 2 ) for n ~ 1000-3000 O(n 3 ) for n ~ 100-200 O(n 4 ) for n ~ 50 O(k n ) or O(n!) for little n, normally < 20 Keep at the top of the priority list The consistent of the calculations (counting the usage) Computers change in velocities, so the time required will be distinctive Therefore recall to test the program/PC before making presumptions!

Problem I have actualized bubble sort for an Array A[N] and connected twofold hunt on it. Time intricacy of air pocket sort? O(N 2 ). Doubtlessly. Time multifaceted nature of double pursuit? O( lg N) Well, what is the time multifaceted nature of my calculation?

Properties O(f) + O(g) = max(O(f), O(g)) O(f) * O(g) = O(fg) So, what is the answer with respect to past question?

Some different documentations (discretionary) (Again no compelling reason to recollect that them) f(N) is Θ (g(N)) iff f(N) is O(g(N)) and g(N) is O(f(N)) f(N) is o(g(N)) For all C, there exists N 0 to such an extent that |f(N)| < C|g(N)| for all N > N 0 f(N) is Ω (g(N)) iff g(N) is O(f(N))

Difficulty of Problem You just need an unpleasant thought regarding this … Definitions (not all that right) An issue with request being a polynomial is called polynomial-time resolvable (P) An issue whose arrangement is confirmed in polynomial time is said to be polynomial-time unquestionable (NP) An issue with no known polynomial-time answer for date is called NP-hard Difficulty of issues are generally named: Easy: in P (obviously all P issues are likewise in NP) Hard: in NP however not in P (NP-finish) Very Hard: not even in NP

" Philosophy " of OI Competitions Objective of Competition … The victor is dictated by: Fastest Program? Measure of time utilized as a part of coding? Number of Tasks Solved? Utilization of the most troublesome calculation? Most astounding Score? Along these lines, amid an opposition, plan to get most elevated score, no matter what – " All is reasonable in affection and war. "

Scoring A " black box " judging framework Test information is nourished into the program Output is checked for rightness No source code is physically investigated How to exploit (without tricking obviously!) of the framework?

The OI Programming Process Reading the issues Choosing an issue Reading the issue Thinking Coding Testing Finalizing the program

Reading the Problem Usually, an assignment comprises of Title Problem Description Constraints Input/Output Specification Sample Input/Output Scoring

Reading the Problem Constraints Range of factors Execution Time NEVER make presumptions yourself Ask at whatever point you are not certain (Do not be reluctant to make inquiries!) Read each word painstakingly Make beyond any doubt you comprehend before going on

Thinking Classify the issue Graph? Arithmetic? Information Processing? Dynamic Programming? and so on … . Some convoluted issues might be a blend of the above Draw graphs, utilize harsh work, jot … Consider extraordinary cases (littlest, biggest, and so on) Is the issue excessively basic? Normally the issue setters have something they need to test the candidates, perhaps a calculation, some particular perceptions, watchfulness and so on. Still no thought? Surrender. Time is valuable.

Designing the Solution Remember, before coding, you MUST have a thought what you are doing. In the event that you wear " t comprehend what you are doing, don't start coding. A few focuses to consider: Execution (Time many-sided quality) Memory utilization (Space many-sided quality) Difficulty in coding Remember, amid rivalry, utilize the calculation that increases you most score, not the speediest/hardest calculation!

Coding Optimized for simplicity of coding, not for perusing Ignore all the " coding rehearses " outside, unless you discover them especially helpful in OI rivalries No Comments required Short factor names Use less capacities NEVER utilize 16 bit whole numbers (unless memory is restricted) 16 bit whole number might be slower! (PC " s are generally 32-bit, even 64 bit designs ought to be to some degree enhanced for 32 bit)

Coding Feel allowed to utilize goto , soften , and so forth up the fitting circumstances Never mind what Djikstra needs to state  Avoid utilizing drifting point factors if conceivable (eg. genuine, twofold, and so forth) Do not do little (otherwise known as pointless) " enhancements " to your code Save and order as often as possible See case program code …

Testing To ensure our program functions of course This is a critical stride, yet generally neglected by challengers

Why Testing? Which of the accompanying is all the more disappointing? You have totally no clue on a troublesome issue You know the arrangement of a troublesome issue, invest hours to code it, however there is an inept bug that you neglect to notice, you get 0 stamps at last Well, the second case is entirely regular

Why Testing? In all OI rivalries, you present a program before rivalry closes. Entries are not judged until the end of rivalry There is no " take two " , no risk to remedy any mix-ups

Testing Sample Input/Output " An issue has test yield for two reasons: To make you comprehend what the right yield configuration is To make you trust that your inaccurate arrangement has tackled the issue effectively  " Manual Test Data Generated Test Data (if time permits) Boundary Cases (0, 1, other littlest cases) Large Cases (to check for TLE, floods, and so forth) Tricky Cases

Debugging – discover the bug, and evacuate it Easiest strategy: writeln/printf/cout It is purported " Debug message " Use of debuggers: FreePascal IDE debugger gdb debugger

Finalizing Check yield organize Any trailing spaces? Missing end-of-lines? (for printf clients, this is entirely regular) better test yet again with test yield Remember to clear those investigate messages Check I/O – filename? stdio? Check exe/source record name Is the executable redesigned? (In the event that exe must be submitted) Method of accommodation? Attempt to designate ~5 mins toward the end of rivalry for settling

Interactive Tasks Traditional Tasks Give contribution to one go Give yield in one go Interactive Tasks Your program is given some information Your program gives some yield Your program is given some more info Your program gives more yield … and so on

Example " Guess the number " Sample Run: Judge: I have a number somewhere around 1 and 5, would you be able to figure? Program: is it 1? J: Too little P: 3? J: Too little P: 5? J: Too huge P: 4? J: Correct P: Your number is 4!

Open Test Data Test information is known Usually entirely hard to tackle Some need tedious calculations, along these lines you are given a couple of hours (i.e. rivalry time) to run the program Tricks: ALWAYS take a gander at all the test information first Solve by hand, physically Solve mostly by program, halfway by hand Some with various projects Solve all with one program (now and then unimaginable!) Make great utilization of existing devices – you don't ha