A Prologue to Programming Ideas and OI-programming

2664 days ago, 945 views
PowerPoint PPT Presentation
What is an Algorithm? From Wikipedia: A calculation is a limited arrangement of all around characterized guidelines for ... Online Google, Wikipedia. HKOI Newsgroup, preparing sites of ...

Presentation Transcript

Slide 1

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

Slide 2

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

Slide 3

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

Slide 4

" 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

Slide 5

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

Slide 6

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

Slide 7

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

Slide 8

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

Slide 9

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?

Slide 10

Complexity (cont " d) Here " s why:

Slide 11

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

Slide 12

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?

Slide 13

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 = ?

Slide 14

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!

Slide 15

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?

Slide 16

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?

Slide 17

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))

Slide 18

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

Slide 19

" 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. "

Slide 20

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?

Slide 21

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

Slide 22

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

Slide 23

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

Slide 24

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.

Slide 25

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!

Slide 26

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)

Slide 27

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 …

Slide 28

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

Slide 29

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

Slide 30

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

Slide 31

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

Slide 32

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

Slide 33

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

Slide 34

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

Slide 35

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!

Slide 36

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