School Assignment? Project Due Tomorrow? Chat LIVE With A Programming Expert!

Programming Help

Web Development



What's Here?

  • Members: 307,096
  • Replies: 841,725
  • Topics: 140,663
  • Snippets: 4,467
  • Tutorials: 1,166
  • Total Online: 2,030
  • Members: 140
  • Guests: 1,890

Welcome to Dream.In.Code
Become an Expert!

Join 307,096 Programmers for FREE! Get instant access to thousands of experts, tutorials, code snippets, and more! There are 2,030 people online right now. Registration is fast and FREE... Join Now!




question in algorithms (d&c)

 

question in algorithms (d&c)
efwa

1 Nov, 2009 - 12:08 PM
Post #1

New D.I.C Head
*

Joined: 1 Nov, 2009
Posts: 2
I need to make a divide&conquer algorithm for finding the dominant element in an array (dominant element = element which exists at least n/2 times in an array within the size n) . All you can do between those elements is compare them (no < relation or > relation) .
Please help me because I'm really lost here...

This post has been edited by efwa: 1 Nov, 2009 - 12:08 PM

User is offlineProfile CardPM
+Quote Post


KYA

RE: Question In Algorithms (d&c)

1 Nov, 2009 - 07:47 PM
Post #2

#include <nerd.h>
Group Icon

Joined: 14 Sep, 2007
Posts: 11,499



Thanked: 508 times
Dream Kudos: 2875
Expert In: C, C++, Java

My Contributions
Is it sorted? Are you allowed extraneous storage? (i.e. the storage of the # of times the element occurs?)

There are a few calculations it should do before it divides and conquers (a modified binary search comes to mind).

Details please.
User is online!Profile CardPM
+Quote Post

efwa

RE: Question In Algorithms (d&c)

2 Nov, 2009 - 12:13 AM
Post #3

New D.I.C Head
*

Joined: 1 Nov, 2009
Posts: 2
This is all the information in the question , so... There's no known sort , and I assume you can save the data within another storage space .
User is offlineProfile CardPM
+Quote Post

LaFayette

RE: Question In Algorithms (d&c)

3 Nov, 2009 - 07:43 AM
Post #4

D.I.C Regular
Group Icon

Joined: 24 Nov, 2008
Posts: 258



Thanked: 29 times
Dream Kudos: 25
My Contributions
By "comparing" I assume that you can test them for equality only.

So, assume at the combine step you have to list A and B that you have recursively solved the problem for and are returned information from both on whether they have a dominant element and references to these if they exists.
There are a few outcomes from this: One of them has it, both of them do, or neither of them do. What conclusion can you draw and how do you test if there is a dominant element in the combined list A+B (in O(n) time preferably)?

I'm leaving the rest for you to figure out for now.

This post has been edited by LaFayette: 3 Nov, 2009 - 07:45 AM
User is offlineProfile CardPM
+Quote Post

Fast ReplyReply to this topicStart new topic

Time is now: 11/21/09 11:51AM
Invision Power Board v2.1.7 © 2009  IPS, Inc.
Licensed to: MediaGroup1

Live Help!

Be Social

Dream.In.Code RSS Feed Dream.In.Code LinkedIn Group Follow Us On Twitter Fan Us On Facebook

Tutorials

Programming

Web Development

Reference Sheets

Code Snippets

DIC Chatroom

Bye Bye Ads

Monthly Drawing

Thumb Drive

Top Contributors

Top 10 Kudos This Month